def mat_mult(a, b):
    """矩阵乘法"""
    n = len(a)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                res[i][j] += a[i][k] * b[k][j]
    return res


def mat_pow(mat, power):
    """矩阵快速幂"""
    # 初始化为单位矩阵
    n = len(mat)
    result = [[int(i == j) for j in range(n)] for i in range(n)]

    while power > 0:
        if power % 2 == 1:
            result = mat_mult(result, mat)
        mat = mat_mult(mat, mat)
        power //= 2
    return result
